#include"graph.h"

//此文件基于点、线类以及图的构造，列出了路径查找的相关功能

// 用于优先队列比较的函数对象
struct Compare {
	bool operator()(const pair<Dot*, double>& a, const pair<Dot*, double>& b) {
		return a.second > b.second; // 较大的优先级高，确保队列是按距离递增顺序
	}
};

// 通过自己创建的数据结构写Dijkstra算法，返回最短路径，并通过引用参数返回最短路径距离
vector<Dot*> Dijkstra(Dot* source, Dot* target, double& minDistance) {
	priority_queue<pair<Dot*, double>, vector<pair<Dot*, double>>, Compare> pq;       //优先队列
	vector<bool> visited(DotKu.size(), false); // 标记顶点是否被访问
	vector<double> distance(DotKu.size(), INT_MAX); // 存储从源点到各顶点的距离
	vector<Dot*> prev(DotKu.size(), nullptr); // 存储到达每个顶点的前一个顶点

	if (DotSearch.find(source) == DotSearch.end()) {
		throw"Error:The source doesn't exist";
	}
	// 初始化
	distance[DotSearch[source]] = 0;
	pq.push(make_pair(source, 0));

	while (!pq.empty()) {
		Dot* current = pq.top().first;
		pq.pop();

		if (visited[DotSearch[current]]) { continue; } // 如果已经访问过，跳过
		visited[DotSearch[current]] = true;

		// 遍历所有相邻的边
		for (const Ray& ray : current->Connection) {
			if (!visited[DotSearch[ray.dot]]) {
				double newDist = distance[DotSearch[current]] + ray.length;
				if (newDist < distance[DotSearch[ray.dot]]) {
					distance[DotSearch[ray.dot]] = newDist; // 更新最短距离
					prev[DotSearch[ray.dot]] = current; // 更新前驱节点
					pq.push(make_pair(ray.dot, newDist));
				}
			}
		}
	}

	minDistance = distance[DotSearch[target]]; // 返回最短路径距离
	// 通过prev数组回溯找到最短路径
	vector<Dot*> path;
	for (Dot* at = target; at != nullptr; at = prev[DotSearch[at]]) {
		path.push_back(at);
	}
	reverse(path.begin(), path.end()); // 确保路径是从源点到终点
	return path;
}

// 通过自己创建的数据结构写Floyd算法，返回最短路径，并通过引用参数返回最短路径距离
vector<Dot*> Floyd(Dot* source, Dot* target, double& minDistance) {
	int n = DotKu.size();
	vector<vector<double>> dist;  // 用于存储最短路径距离的矩阵
	dist.resize(n, vector<double>(n, INT_MAX)); // 初始化距离矩阵

	// 初始化距离矩阵
	for (int i = 0; i < n; i++) {
		for (const Ray& ray : DotKu[i]->Connection) {
			dist[i][DotSearch[ray.dot]] = ray.length; // 设置直接连接的顶点间的距离
		}
		dist[i][i] = 0; // 顶点到自身的距离为0
	}

	// 执行Floyd-Warshall算法
	for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				// 如果通过顶点k的路径比现有路径更短，则更新距离
				if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX && dist[i][k] + dist[k][j] < dist[i][j]) {
					dist[i][j] = dist[i][k] + dist[k][j];
				}
			}
		}
	}

	// 检查源点到终点的最短路径距离
	minDistance = dist[DotSearch[source]][DotSearch[target]];
	if (minDistance == INT_MAX) {
		throw"Error:Can't find path"; // 不存在路径
	}

	// 通过距离矩阵重建最短路径
	vector<Dot*> path;
	path.push_back(target);
	int current = DotSearch[target];
	while (current != DotSearch[source]) {
		// 从终点开始，回溯到源点
		for (int i = 0; i < n; i++) {
			if (dist[i][current] + dist[current][DotSearch[target]] == dist[i][DotSearch[target]] && dist[i][current] != INT_MAX) {
				path.push_back(DotKu[i]); // 添加到路径中
				current = i; // 移动到下一个顶点
				break;
			}
		}
	}
	path.push_back(source);
	reverse(path.begin(), path.end()); // 确保路径是从源点到终点
	return path;
}


/*以下是路径查找功能，结合图的深度优先算法、回溯以及剪枝实现
功能描述：传入起点和重点，获取多条路径和其对应的长度，路径个数小于等于5且按路径长度排列，且获得的路径均小于等于用Dijkstra或Floyd算法
获取的最短路径*1.5，即路径个数=min（5，路径小于等于用Dijkstra或Floyd算法获取的最短路径*1.5的符合要求路径的总个数）
此功能便于后面扩展导航功能中最短时间策略的选取，也为用户提供了多种道路的可选择性，灵活运用了深度优先搜索算法
*/

// 深度优先搜索（DFS）实现路径的查找
void FindRoot_DFS(Dot* current, Dot* target, double maxLen, vector<Dot*>& path, vector<vector<Dot*>>& paths, vector<double>& pathLengths, double& currentPathLen) {
	if (current == target) { // 如果到达终点
		paths.push_back(path); // 添加路径到结果中
		pathLengths.push_back(currentPathLen); // 添加路径长度
		return;
	}
	for (const Ray& ray : current->Connection) {
		if (currentPathLen + ray.length <= maxLen) {   //如果路径超过最短路径*1.5，则剪枝
			path.push_back(ray.dot); // 添加顶点到路径
			currentPathLen += ray.length; // 更新路径长度
			FindRoot_DFS(ray.dot, target, maxLen, path, paths, pathLengths, currentPathLen); // 递归搜索
			currentPathLen -= ray.length; // 回溯路径长度
			path.pop_back(); // 回溯
		}
	}
}

// 查找所有满足条件的路径，并通过引用参数返回每条路径对应的最短路径距离，返回的最短路径以及距离根据路径长度进行排序
vector<vector<Dot*>> FindRoot(Dot* source, Dot* target, vector<double>& pathLengths) {
	double minDistance;
	vector<vector<Dot*>> paths;
	vector<Dot*> path;
	vector<double> tempPathLengths; // 临时存储路径长度
	path.push_back(source); // 添加源点

	// 使用Dijkstra或Floyd算法算法计算最短路径
	Floyd(source, target, minDistance);

	double maxLen = minDistance * 1.5; // 设置最大路径长度
	double currentPathLen = 0; // 当前路径长度

	// 执行深度优先搜索
	FindRoot_DFS(source, target, maxLen, path, paths, tempPathLengths, currentPathLen);

	// 创建一个路径和长度的配对列表，以确保排序的时候路径和长度是绑定的
	vector<pair<vector<Dot*>, double>> pathsWithLengths;
	for (size_t i = 0; i < paths.size(); i++) {
		pathsWithLengths.emplace_back(paths[i], tempPathLengths[i]);
	}

	// 根据路径长度对路径和长度的配对列表进行排序
	sort(pathsWithLengths.begin(), pathsWithLengths.end(), [](const pair<vector<Dot*>, double>& a, const pair<vector<Dot*>, double>& b) {
		return a.second < b.second;
		});

	// 清空原来的路径和长度列表
	paths.clear();
	pathLengths.clear();

	// 从排序后的配对列表中提取路径和长度
	for (int p = 0; p < pathsWithLengths.size(); p++) {
		paths.push_back(pathsWithLengths[p].first);
		pathLengths.push_back(pathsWithLengths[p].second);
	}

	// 保留最短的5条路径
	paths.resize(min(5, paths.size()));
	pathLengths.resize(min(5, pathLengths.size()));

	return paths;
}

/*以下功能是校车导航的子模块，用于查找距离定点的最近的公交站
* 并获取定点到公交站的路径和距离
*/

bool BFS(Dot* source, Dot*& nearestStation, vector<Dot*>& path, double& minDistance, map<Dot*, double> &distances) {
	queue<std::pair<Dot*, double>> q; // 队列存储点以及到源点的距离
	map<Dot*, bool> visited; // 访问标记

	// 初始化源点距离为0
	distances[source] = 0.0;
	q.push(std::make_pair(source, 0.0));
	visited[source] = true;

	while (!q.empty()) {
		Dot* current = q.front().first;
		double currentDistance = q.front().second;
		q.pop();

		// 如果当前点是公交站，并且距离小于已知最小距离，更新最近站点和最小距离
		if (current->type == 1 && (minDistance == 999999999999 || currentDistance < minDistance)) {
			minDistance = currentDistance;
			nearestStation = current;
			// 由于我们需要构建路径，我们需要继续搜索直到找到最近站点
		}

		// 遍历所有相连的点
		for (const Ray& ray : current->Connection) {
			if (!visited[ray.dot]) {
				visited[ray.dot] = true;
				distances[ray.dot] = currentDistance + ray.length;
				q.push(std::make_pair(ray.dot, currentDistance + ray.length));
			}
			else if (distances[ray.dot] > currentDistance + ray.length) {
				// 如果找到了更短的路径，则更新并重新入队
				distances[ray.dot] = currentDistance + ray.length;
				q.push(std::make_pair(ray.dot, currentDistance + ray.length));
			}
		}
	}
	return nearestStation != nullptr;
}

Dot* GetNearestStation(Dot* source,vector<Dot*>& path, double& length) {
	Dot* nearestStation = nullptr;
	double minDistance = 999999999999; // 初始化为最大值
	map<Dot*, double> distances;   //表示每个点到源点的最短距离

	if (BFS(source, nearestStation, path, minDistance, distances)) {
		// 重建路径
		Dot* current = nearestStation;
		length = minDistance;
		path.push_back(current);

		// 从终点反向遍历找到路径
		while (current != source) {
			for (const Ray& ray : current->Connection) {
				if (ray.dot != source && distances[ray.dot] + ray.length == distances[current]) {
					current = ray.dot;
					path.push_back(current);
					break;
				}
			}
		}
		path.push_back(source);
		reverse(path.begin(), path.end()); // 反转路径以使源点在路径的开始位置
	}
	return nearestStation;
}